package cn.ly.sort.insert;

public class ArrayIns {
	
	private int[] a;
	private int nElems;
	
	public ArrayIns(int size){
		a = new int[size];
		this.nElems = 0;
	}
	
	public void insert(int value){
		a[nElems] = value;
		this.nElems++;
	}
	
	public void display(){
		for(int i=0; i < this.nElems; i++){
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	//插入排序
	public void insertSort(){
		int temp = 0;
		for(int i=1; i < nElems; i++){      //从数组第二个位置开始做排序，把第一个位置的当成一个有序的数组
			temp = a[i];
			int j = i;
			/*for(; j < i; j++){       //实际上就是把这个数组当成两个数组，前变一部分是已经排好序的数组，后面的元素往前面的数组里面插入到合适的位置
				if(a[j]>temp){         //这种将前面有序数组，从前往后比较的找到插入位置的方式不行，因为当找到合适位置后，还要将后面的数据，向后
					a[j+1] = a[j];     //这样又要再用一个循环，这样的算法时间复杂度太高了，但是用从后往前寻找插入位置的方法是把查找和移动同时做的，
				}                      //比从前往后找减少一半工作量
			}*/
			for( ;j > 0 && a[j-1] >= temp; j--){
				a[j] = a[j-1];                       //因为是把前一个元素先后移动，所以a[1-1]，所以是j > 0，不能j=0
			}
			a[j] = temp;
			/*while(j>0 && a[j-1]>=temp){//从后往前比较
				a[j] = a[j-1];
				j--;
			}*/
			
		}
	}
	
	

}
